//给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
//注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

//此题最普遍的解法是直接进行中序遍历，将结果存储到一个顺序表中，然后返回pNode的下一个索引位置的节点即可
//时间复杂度和空间复杂度都为O(n)。

//但明显有更方便的解法，直接分析pNode所在位置的情况，进而分析每种情况下pNode的下一个节点
//主要考察队中序遍历的了解，pNode可能为非叶子节点，也可能为叶子结点，提供next访问父节点反而方便了遍历
//时间复杂度为O(n),空间复杂度为O(1)。

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
class Solution{
	public TreeLinkNode GetNext(TreeLinkNode pNode){
		if(pNode.right!=null){//如果pNode的位置是非叶子结点,那么根据中序遍历的特点，
							  //下一个节点一定在pNode的右子树的最左边
		TreeLinkNode cur=pNode.right;
		while(cur.left!=null){
			cur=cur.left;
			}
		return cur;
		}
		//如果pNode的位置是叶子结点，那么分为左结点和右节点两种情况
		if(pNode.next!=null&&pNode.next.left==pNode){//pNode为左结点的情况
			return pNode.next;
		}
		if(pNode.next!=null&&pNode.next.right==pNode){//pNode为右节点的情况
			TreeLinkNode cur=pNode.next;
			while(cur.next!=null&&cur.next.right==cur){
				cur=cur.next;
			}
			return cur.next;
		}
	return null;//都不满足的情况，返回null
	}
}